package com.cdream.basic.algorithm.leetcode.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author cdream
 * @date 2022/3/20
 */
public class Question2039 {
    public static void main(String[] args) {
        // new Question2039().networkBecomesIdle(new int[][]{{0,1},{0,2},{1,2}},new int[]{0,10,10});
    }
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;
        List<Integer>[] path = new List[n];
        for(int i = 0; i<n ;i++){
            path[i] = new ArrayList<>();
        }
        for(int[] edge: edges){
            path[edge[0]].add(edge[1]);
            path[edge[1]].add(edge[0]);
        }
        boolean used[] = new boolean[n];
        int[] dists = new int[n];
        LinkedList<Integer> stack = new LinkedList<Integer>();
        stack.push(0);
        used[0] = true;

        while(!stack.isEmpty()){
            int size = stack.size();
            for(int i = 0; i<size;i++){
                int poll = stack.poll();
                int dist = dists[poll];
                List<Integer> children = path[poll];
                for(int child : children){
                    if(used[child]){
                        continue;
                    }
                    stack.offer(child);
                    dists[child] = dist + 1;
                    used[child]=true;
                }
            }
        }
        int max = 0;
        for(int i = 1; i<n;i++){
            max = Math.max(max , patience[i]*(2*dists[i]-1)/patience[i]+2 * dists[i] + 1);
        }
        return max;
    }
}
